package cn.nit.algorithm.experiment;


/**
 * @author LXQ
 * @version 1.0
 * @date 2021/6/4 6:28
 */
//KMP算法，字符串匹配

public class Experiment7 {
    String target="ilikealgorithmverymuchforeverhhhhha";
    String mode="like";
    public String totalString="";

    public Experiment7(){
    }

    public Experiment7(String child){
        mode = child;
    }

//    public static void main(String[] args) {
//        Experiment7 kmp = new Experiment7();
//        boolean result=kmp.mathString(kmp.target,kmp.mode);
//        if(!result){
//            System.out.println("主串:"+kmp.target);
//            System.out.println("子串:"+kmp.mode);
//            System.out.println("没有找到匹配的子串");
//        }
//    }

    public String runMain(){
        boolean result=mathString(target,mode);
        if(!result){
            System.out.println("主串:"+target);
            totalString+="主串:"+target+"<br>";
            System.out.println("子串:"+mode);
            totalString+="子串:"+mode+"<br>";
            System.out.println("没有找到匹配的子串");
            totalString+="没有找到匹配的子串<br>";
        }
        return totalString;
    }

    public boolean mathString(String target, String mode) {
        int[] next = getNextArray(mode);
        int i = 0;
        int j = 0;
        while (i < target.length() && j < mode.length()) {
            if (j == 0 || target.charAt(i) == mode.charAt(j)) {
                i++;
                j++;
            }
            else {
                if(next[j]==-1){
                    j=0;
                    i++;
                }else{
                    j=next[j];
                }
            }

        }
        if (j == mode.length()){
            System.out.println("主串:"+target);
            totalString+="主串:"+target+"<br>";
            System.out.print("子串:");
            totalString+="子串:";
            for(int t=0;t<i-mode.length();t++){
                System.out.print(" ");
            }
            System.out.println(mode);
            totalString+=mode+"<br>";
            System.out.println("主串匹配的位置从:"+(i-mode.length()+1)+"到"+i);
            totalString+="主串匹配的位置从:"+(i-mode.length()+1)+"到"+i+"<br>";
            return true;
        }

        return false;
    }

    public int[] getNextArray(String mode) {
        int j = 0, k = -1;
        int[] next = new int[mode.length()];
        next[0] = -1;
        while (j < mode.length()-1) {
            if (k == -1 || mode.charAt(j) == mode.charAt(k)) {
                ++j;
                ++k;
                if (mode.charAt(j) != mode.charAt(k)) {
                    next[j] = k;
                } else {
                    next[j] = next[k];
                }
            }
            else
                k = next[k];
        }
        return next;
    }

}

